Traversarea in latime - BF

- se porneste de la un nod si se parcurg toate nodurile adiacente lui
- apoi se parcurg toti vecinii acestora , care nu au fost inca parcursi
- se continua pana au fost vizitate toate nodurile grafului

Code :

// BF cu liste de legatura 

#include <fstream>
using namespace std;

ifstream F("bf.in");
ofstream G("bf.out");

#define Nmax 1011 

int N,M;
int Leg[Nmax][Nmax];
int Lung[Nmax];

int x,y;
int Coada[Nmax],Co;
int Coada2[Nmax],Co2;

void BF(int Nod,int Step,int Stop)
{
	Lung[Nod]=Step;
	Coada[++Co]=Nod;
	
	for (; !Lung[Stop] ; ++ Step )
	{
		for (int i=1;i<=Co;++i)
			for (int j=1;j<=Leg[Coada[i]][0];++j)
			{
				if ( Lung[ Leg[Coada[i]][j] ]==0 )
				{
					Lung[ Leg [Coada[i]][j] ]=Step+1;
					Coada2[++Co2]=Leg[Coada[i]][j];
				}
				if ( Lung[Stop] ) return;
			}
		for (int i=1;i<=Co2;++i)
			Coada[i]=Coada2[i];
		Co=Co2;
		Co2=0;
	}
}

int main()
{
	F>>N>>M;
	for (int i=1;i<=M;++i)
	{
		F>>x>>y;
		Leg[x][++Leg[x][0]]=y;
		Leg[y][++Leg[y][0]]=x;
	}
	
	F>>x>>y;
	
	BF(x,1,y);
	
	G<<Lung[y]-1<<'\n';
}

